package com.wtgroup.demo.mianshi.算法.字符串.字符串匹配;

import org.junit.Assert;

import java.util.ArrayList;
import java.util.List;

/**
 * 暴力子字符串匹配
 *
 * @author L&J
 * @version 0.0.0
 * @email liuhejun108@163.com
 * @date 2019/9/19 10:30
 */
public class SimpleStrMatcher {
    public static void main(String[] args) {
        String str = "74u54r加条用ge噢哟";
        int pos = search("用", str);
        Assert.assertEquals(pos, 8);
        System.out.println(search("4", str));
    }

    public static List<Integer> matching( String p, String str) {
        List<Integer> res = new ArrayList<Integer>();
        int n = str.length();
        int m = p.length();
        for ( int i = 0; i <= n-m; i++ ) {
            int j=0;
            while ( j<m && str.charAt(i+j) == p.charAt(j) ){j++;};
            if ( j==m ) {
                // 匹配到一个模式
                res.add(i);
            }
        }
        return res;
    }


    /**启发式改造: 指针回退
     * ? 复杂度不变, 注重"回退"思想 ?
     * @param str 字符串
     * @param p 模式
     * @return 返回匹配处开始索引
     */
    public static int search(String str, String p) {
        int n = str.length();
        int m = p.length();
        int i = 0, j = 0;
        for (; i <= n-m && j < m; i++) {
            if (str.charAt(i) == p.charAt(j)) {
                j++;
            }
            // 回退
            else {
                i -= j;
                j = 0;
            }
        }
        if (j==m) {
            // 找到匹配，返回开始处索引
            return i-m;
        }
        return -1;
    }

}
